﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Threading.Tasks;
using System.Runtime.InteropServices;
using alib.Debugging;

using alib.Hashing;
using alib.Enumerable;
using alib.Collections;
using alib.Array;

namespace alib.dg
{
	using String = System.String;
	using Enumerable = System.Linq.Enumerable;
	using Array = System.Array;
	using alib.dg.debug;


	public interface IGraph
	{
		dg.Edge[] Edges { get; }
		int EdgeCount { get; }
		int EdgeAlloc { get; }
		dg.Vertex[] Verticies { get; }
		int VertexCount { get; }
		int VertexAlloc { get; }
		String vertex_string(Vref vr);
		String edge_string(Eref er);
	};

	public interface IEditGraph : IGraph
	{
	};

	public interface IEdata<out TEdge> : IGraph
	{
		TEdge EdgeData(Eref e);
	};
	public interface IEindex<TEdge> : IEdata<TEdge>
	{
		IIndexedHash<TEdge> EDict { [DebuggerStepThrough] get; }
	};

	public interface IVdata<out TVertex> : IGraph
	{
		TVertex VertexData(Vref v);
	};
	public interface IVindex<TVertex> : IVdata<TVertex>
	{
		IIndexedHash<TVertex> VDict { [DebuggerStepThrough] get; }
	};

	public interface IGraphData<TEdge, TVertex> : IEindex<TEdge>, IVindex<TVertex>
	{
	};

	public interface IStringGraph : IGraph, IGraphData<String, String>
	{
	};

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	///
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

	public static class _dg_ext
	{
		public static Eref vertex_first_edge(this IGraph g, Vref v)
		{
			return ((dg)g).V[v].e_out;
		}
		public static int vertex_out_edge_count(this IGraph g, Vref v)
		{
			return ((dg)g).V[v].c_out;
		}
		public static bool vertex_is_leaf(this IGraph g, Vref v)
		{
			return ((dg)g).V[v].c_out == 0;
		}
		public static bool vertex_is_top(this IGraph g, Vref v)
		{
			return ((dg)g).V[v].e_in == Eref.None;
		}
		public static Eref vertex_master_edge(this IGraph g, Vref v)
		{
			return ((dg)g).V[v].e_in;
		}
		public static Eref edge_next_peer(this IGraph g, Eref e)
		{
			return ((dg)g).E[e].e_next;
		}
		public static Vref edge_target(this IGraph g, Eref e)
		{
			return ((dg)g).E[e].v_to;
		}

		public static bool edge_is_valid(this IGraph g, Eref er)
		{
			return ((dg)g).edge_is_valid(er);
		}
		public static IEnumerable<int[]> edge_paths(this IGraph g, Eref e)
		{
			return ((dg)g).edge_paths(e);
		}
		public static bool edge_is_master(this IGraph g, Eref e)
		{
			return ((dg)g).edge_is_master(e);
		}
		public static Vref edge_parent(this IGraph g, Eref e)
		{
			return ((dg)g).edge_parent(e);
		}
		public static bool edge_is_coref_and_master(this IGraph g, Eref e)
		{
			return ((dg)g).edge_is_coref_and_master(e);
		}
		public static int edge_peer_count(this IGraph g, Eref e)
		{
			return ((dg)g).edge_peer_count(e);
		}
		public static bool vertex_is_valid(this IGraph g, Vref vr)
		{
			return ((dg)g).vertex_is_valid(vr);
		}
		public static Eref[] vertex_in_edges(this IGraph g, Vref v)
		{
			return ((dg)g).vertex_in_edges(v);
		}
		public static void vertex_switch_master_edge(this IGraph g, Vref v, Eref e_new)
		{
			((dg)g).vertex_switch_master_edge(v, e_new);
		}
		public static IEnumerable<String> path_strings(this IGraph g, Eref e)
		{
			if (!g.edge_is_valid(e))
				yield break;
			foreach (var p in g.edge_paths(e))
			{
				//yield return dict.ConvertTo(p).StringJoin(".");
			}
		}
		public static void check(this IGraph g)
		{
			var rwg = g as rw_graph;
			if (rwg != null)
				rwg.check();
		}
		public static void delete_edge(this IGraph g, Eref er)
		{
			var rwg = g as rw_graph;
			if (rwg == null)
				throw new Exception();
			rwg.delete_edge(er);
		}
		public static void delete_all_in_edges(this IGraph g, Vref vr)
		{
			var rwg = g as rw_graph;
			if (rwg == null)
				throw new Exception();
			rwg.delete_all_in_edges(vr);
		}
		public static void delete_vertex(this IGraph g, Vref vr)
		{
			var rwg = g as rw_graph;
			if (rwg == null)
				throw new Exception();
			rwg.delete_vertex(vr);
		}
		public static Vref add_vertex(this IGraph g, int value)
		{
			var rwg = g as rw_graph;
			if (rwg == null)
				throw new Exception();
			return rwg.add_vertex(value);
		}
		public static Eref create_edge(this IGraph g, Vref v_from, Vref v_to, int value)
		{
			var rwg = g as rw_graph;
			if (rwg == null)
				throw new Exception();
			return rwg.create_edge(v_from, v_to, value);
		}
	};

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	///
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

	public class GraphException : Exception
	{
		public GraphException(String fmt, params Object[] args)
			: base(String.Format(fmt, args))
		{
		}
	};

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	///
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

	[DebuggerDisplay("{_dbg.ToString(),nq}", Type = "Eref")]
	public struct Eref : IEquatable<Eref>, IComparable<Eref>
	{
		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public static Eref Zero = new Eref(status.Zero);
		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public static Eref None = new Eref(status.None);
		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public static Eref NotValid = new Eref(status.NotValid);

		[DebuggerStepThrough]
		public Eref(int ix) { this.ix = ix; }
		[DebuggerStepThrough]
		public Eref(status es) { this.ix = (int)es; }
		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		int ix;
		[DebuggerStepThrough]
		public static implicit operator int(Eref er) { return er.ix; }
		[DebuggerStepThrough]
		public static implicit operator status(Eref er) { return (status)er.ix; }
		[DebuggerStepThrough]
		public static Eref operator +(Eref er, int i) { return new Eref(er.ix + i); }
		[DebuggerStepThrough]
		public static int operator +(int i, Eref er) { return i + er.ix; }
		[DebuggerStepThrough]
		public static Eref operator ++(Eref er) { return new Eref(er.ix + 1); }
		[DebuggerStepThrough]
		public static Eref operator --(Eref er) { return new Eref(er.ix - 1); }
		[DebuggerStepThrough]
		public static bool operator ==(Eref a, Eref b) { return a.ix == b.ix; }
		[DebuggerStepThrough]
		public static bool operator !=(Eref a, Eref b) { return a.ix != b.ix; }
		[DebuggerStepThrough]
		public int CompareTo(Eref other) { return this.ix - other.ix; }
		[DebuggerStepThrough]
		public bool Equals(Eref other) { return this.ix == other.ix; }
		public override bool Equals(Object obj) { return obj is Eref && ((Eref)obj).ix == this.ix; }
		public override int GetHashCode() { return ix; }

#if DEBUG
		[DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
		public eent_dbg _dbg
		{
			[DebuggerStepThrough]
			get { return new eent_dbg(dg._singleton, this); }
		}
#endif
	};

	[DebuggerDisplay("{_dbg.ToString(),nq}", Type = "Vref")]
	public struct Vref : IEquatable<Vref>, IComparable<Vref>
	{
		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public static Vref Zero = new Vref(status.Zero);
		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public static Vref NotValid = new Vref(status.NotValid);
		[DebuggerStepThrough]
		public Vref(status s) { this.ix = (int)s; }
		[DebuggerStepThrough]
		public Vref(int ix) { this.ix = ix; }
		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		int ix;
		[DebuggerStepThrough]
		public static implicit operator int(Vref vr) { return vr.ix; }
		[DebuggerStepThrough]
		public static explicit operator Vref(int ix) { return new Vref(ix); }
		[DebuggerStepThrough]
		public static Vref operator ++(Vref vr) { return new Vref(vr.ix + 1); }
		[DebuggerStepThrough]
		public static Vref operator --(Vref vr) { return new Vref(vr.ix - 1); }
		[DebuggerStepThrough]
		public static bool operator ==(Vref a, Vref b) { return a.ix == b.ix; }
		[DebuggerStepThrough]
		public static bool operator !=(Vref a, Vref b) { return a.ix != b.ix; }
		[DebuggerStepThrough]
		public int CompareTo(Vref other) { return this.ix - other.ix; }
		[DebuggerStepThrough]
		public bool Equals(Vref other) { return this.ix == other.ix; }
		public override bool Equals(Object obj) { return obj is Vref && ((Vref)obj).ix == this.ix; }
		public override int GetHashCode() { return ix; }
#if DEBUG
		[DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
		public vent_dbg _dbg
		{
			[DebuggerStepThrough]
			get { return new vent_dbg(dg._singleton, this); }
		}
#endif
	};

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	///
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

	[Flags]
	public enum status : int
	{
		Zero /*					*/ = 0,
		_neg /*					*/ = unchecked((int)0x80000000),
		None /*					*/ = _neg /*						*/ | 0x0001,
		NotValid /*				*/ = _neg /*						*/ | 0x0002,
		FreelistTerm /*			*/ = _neg /*						*/ | 0x0003,
		NotInFreelist /*		*/ = _neg /*						*/ | 0x0004,
		free /*					*/ = _neg /*						*/ | 0x0010,
		fe_HasList /*			*/ = free /*						*/ | 0x0020,
		fe_HasSize /*			*/ = free /*						*/ | 0x0040,
		fe_BlockStart /*		*/ = fe_HasSize | fe_HasList /*		*/ | 0x0100,
		fe_BlockEnd /*			*/ = fe_HasSize /*					*/ | 0x0200,
		fe_BlockSingleton /*	*/ = fe_BlockStart | fe_BlockEnd,
	};

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	///
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

	public abstract partial class dg : IGraph
	{
		[DebuggerDisplay("{ToString(dg._singleton),nq}", Type = "dg.Edge")]
		[StructLayout(LayoutKind.Explicit, Size = 16)]
		public struct Edge
		{
			[FieldOffset(0), DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public Vref v_from;
			[FieldOffset(0), DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public int prv;

			[FieldOffset(4), DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public Vref v_to;
			[FieldOffset(4), DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public int nxt;

			[FieldOffset(8), DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public Eref e_next;
			[FieldOffset(8), DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public status status;

			[FieldOffset(12), DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public int value;
			[FieldOffset(12), DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public int block_size;

			/// <summary> debugging only; refer to graph's freelist instead </summary>
			[DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public bool IsFree { [DebuggerStepThrough] get { return (status & status.free) == status.free; } }
			[DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public bool HasSize { [DebuggerStepThrough] get { return (status & status.fe_HasSize) == status.fe_HasSize; } }
			[DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public bool HasList { [DebuggerStepThrough] get { return (status & status.fe_HasList) == status.fe_HasList; } }
			[DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public bool IsBlockSingleton { [DebuggerStepThrough] get { return (status & status.fe_BlockSingleton) == status.fe_BlockSingleton; } }
			[DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public bool IsBlockStart { [DebuggerStepThrough] get { return (status & status.fe_BlockStart) == status.fe_BlockStart; } }
			[DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public bool IsBlockEnd { [DebuggerStepThrough] get { return (status & status.fe_BlockEnd) == status.fe_BlockEnd; } }

			public void reset(status s, int block_size = 0)
			{
				this.status = s;
				this.prv = this.nxt = (int)status.NotInFreelist;
				this.block_size = block_size;
			}

#if DEBUG
			public unsafe Eref _discover_eref()
			{
				long d = -1;
				var arr = dg._singleton.Edges;
				if (arr != null)
					fixed (Edge* _pe = &arr[0], _this = &this)
						d = _this - _pe;
				return d >= 0 && d < arr.Length ? new Eref((int)d) : Eref.NotValid;
			}

			[DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
			public eent_dbg _dbg
			{
				[DebuggerStepThrough]
				get
				{
					var g = dg._singleton;
					return g != null ? new eent_dbg(g, _discover_eref()) : new eent_dbg(null, Eref.NotValid);
				}
			}
			public String ToString(IGraph g)
			{
				Eref er;
				if (g == null || ((er = _discover_eref()) < 0))
					return String.Format("v_from:{0} v_to:{1} e_next:{2} value:{3}",
						(int)v_from,
						(int)v_to,
						(int)e_next,
						value);
				return new eent_dbg(g, er).ToString();
			}

			public override String ToString() { return ToString(dg._singleton); }
#endif
		};

		public struct EdgeRange
		{
			public static readonly EdgeRange NotValid = new EdgeRange(Eref.NotValid, 0);

			public EdgeRange(Eref _start, int _length)
			{
				//Debug.Assert(_length >= 0 && (_start == Eref.NotValid) == (_length == 0));
				this.ix = _start;
				this.c = _length;
			}
			public readonly Eref ix;
			public readonly int c;

			public bool IsValid { get { return ix >= 0; } }

			public bool Contains(Eref e)
			{
				if (!IsValid)
					throw new Exception();
				return ix <= e && e < ix + c;
			}

			public Eref Last
			{
				get
				{
					if (!IsValid)
						throw new Exception();
					return ix + (c - 1);
				}
			}

			public Eref Next
			{
				get
				{
					if (!IsValid)
						throw new Exception();
					return ix + c;
				}
			}
			public Eref PrevEnd
			{
				get
				{
					if (!IsValid)
						throw new Exception();
					return ix + (-1);
				}
			}

			public static int operator -(EdgeRange a, EdgeRange b)
			{
				if (!a.IsValid || !b.IsValid)
					throw new Exception();
				return (int)a.ix - (int)b.ix;
			}

		};

		[DebuggerDisplay("{ToString(dg._singleton),nq}", Type = "dg.Vertex")]
		[StructLayout(LayoutKind.Explicit, Size = 16)]
		public struct Vertex
		{
			[FieldOffset(0), DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public Eref e_in;
			[FieldOffset(0), DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public int prv;

			[FieldOffset(4), DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public Eref e_out;
			[FieldOffset(4), DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public int nxt;

			[FieldOffset(8), DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public int c_out;
			[FieldOffset(8), DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public status status;

			[FieldOffset(12), DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public int value;

			[DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public Eref e_last { get { return e_out + c_out; } }

			public EdgeRange OutEdgeRange
			{
				get { return new EdgeRange(e_out, c_out); }
			}

			[DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public Eref[] out_edges
			{
				get
				{
					if (c_out == 0)
						return NoErefs;
					var arr = new Eref[c_out];
					var e = e_out;
					for (int i = 0; i < c_out; i++, e++)
						arr[i] = e;
					return arr;
				}
			}

			[DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public bool IsLeaf { [DebuggerStepThrough] get { return c_out == 0; } }

			[DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public bool IsTop { [DebuggerStepThrough] get { return e_in == Eref.None; } }

			[DebuggerBrowsable(DebuggerBrowsableState.Never)]
			/// <summary> debugging only; refer to graph's freelist instead </summary>
			public bool IsFree { get { return c_out < 0; } }
#if DEBUG

			public unsafe Vref _discover_vref()
			{
				long d = -1;
				var arr = dg._singleton.Verticies;
				if (arr != null)
					fixed (Vertex* _pv = &arr[0], _this = &this)
						d = _this - _pv;
				return d >= 0 && d < arr.Length ? new Vref((int)d) : Vref.NotValid;
			}

			[DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
			public vent_dbg _dbg
			{
				[DebuggerStepThrough]
				get
				{
					var g = dg._singleton;
					return g != null ? new vent_dbg(g, _discover_vref()) : new vent_dbg(null, Vref.NotValid);
				}
			}

			public String ToString(IGraph g)
			{
				Vref vr;
				if (g == null || ((vr = _discover_vref()) < 0))
					return String.Format("e_in:{0} e_out:{1} c_out:{2} value:{3}",
						(int)e_in,
						(int)e_out,
						(int)c_out,
						value);
				return new vent_dbg(g, vr).ToString();
			}

			public override String ToString() { return ToString(dg._singleton); }
#endif
		};
	};

}
